TSP - 외판원 순회
TSP - 외판원 순회
상태: 정리완료
태그: dp, graph
모든 도시를 한번씩만 들르고
브루트포스
DP
결론:
D[vi][A]
= 집합 A에 속한 정점을 정확히 한 번만 거쳐 vi 에서 v1로 가는 최단경로의 길이
가장 큰 문제 : D[v1][V-{v1}]
V = 전체 정점들의 집합.
가장 작은 문제 : D[vi][{}] = W[i][1]
vi에서 v1로 직빵으로 가는 경로의 길이
for k in 1..<n :
for all A subset of V - {v1} containing k vertices :
for i such that i != 1 and vi is not in A :
for j in A :
vj = V[j]
D[i][A] <- min( W[i][j] + D[vj][A - {vj}] )
시간복잡도
- 첫번째 for문에서 n-1
- 두번째 for문에서 C(n-1, k)
- 세번째 for문에서 n - k - 1 : 아직 방문하지 않은 도시의 개수
- 네번째 for문에서 k